package 力扣._49_字母异位词分组;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<int[]> wordhashlist = new ArrayList<>();  //字母hash
        List<List<String>> list = new ArrayList<>();  //值——异位词
        String word;
        int word_hash_index = -1;
        int k;
        int[] t;
        List<String> word_list;
        for (int i = 0; i < strs.length; i++) {
            word_hash_index = -1;
            word = strs[i];
            //在list中寻找该单词的字母异位词
            for (int j = 0; j < wordhashlist.size(); j++) {
                t = wordhashlist.get(j).clone();    //每个字母的出现次数

                for (k = 0; k < word.length(); k++) {
                    char c = word.charAt(k);
                    t[c - 'a'] -= 1;
                }
                // word的每个字母都要在hash表中出现，且此时t中全为0才算匹配成功
                int q;
                for (q = 0; q < 26; q++)
                    if (t[q] != 0)
                        break;

                if (q == 26) {//匹配成功
                    word_hash_index = j;
                    break;
                }
            }

            if (word_hash_index == -1) {  //若不存在，则创建字母hash，异位词列表，并添加到列表中
                t = new int[26];
                for (k = 0; k < word.length(); k++) {
                    char c = word.charAt(k);
                    t[c - 'a'] += 1;
                }
                wordhashlist.add(t);
                word_list = new ArrayList<>();
                word_list.add(word);
                list.add(word_list);

            } else {  //若存在，则将该词添加到列表中
                word_list = list.get(word_hash_index);
                word_list.add(word);
            }


        }
        return list;
    }

    public static void main(String[] args) {

        String[] strs = new String[2];
        strs[0] = "ac";
        strs[1] = "c";
//        strs[2] = "";
        List<List<String>> lists = new Solution().groupAnagrams(strs);
        System.out.printf(lists.toString());
    }
}